package hxg.com.algorithm;

import java.util.Scanner;

/**
 * @author HeXiangGuang
 * @create 2022-06-16 10:03
 * 题目 G:数列构造
 * 给定一个正整数 k(3<=k<=15),把所有 k 的方幂及所有有限个互不相等的 k 的方幂之和
 * 构成一个递增的序列.例如.当 h = 3 时，这个序列是：
 * 1,3,4,9.10,12,13……
 * 该序列实际上就是：
 * 3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^l+3^2…
 * 请你求出这个序列的第 N 项的值（用十进制数表示）。
 * 例如，对于 k= 3,N=100,正确答案应该是 981。
 * 该算法的时间复杂度为循环计算二进制数组中的10进制值的次数为O(array.lenght)
 * 也就是说该算法的时间复杂度为O(n)
 * 该算法的空间复杂度为创建数组array的元素个数O(array.lenght)
 * 也就是说该算法的空间复杂度为O(n)
 */
public class ArrayConstruction {
    public static void main(String[] args)
    {
        //k,n为输入的整数的方幂和所要求的第n项,sum为实际数,number为输入n项数记录值
        int k,n;
        long sum = 0;
        //定义控制台输入
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入k的值：");
        k = scanner.nextInt();
        while (!isInputK(k))
        {
            System.out.println("输入错误请重新输入：");
            k = scanner.nextInt();
        }
        System.out.println("请输入n项的值：");
        n = scanner.nextInt();
        while (!isNumeric(n))
        {
            System.out.println("请输入一个正整数！");
            System.out.println("输入错误请重新输入：");
            n = scanner.nextInt();
        }
        int number = n;
        //获取开始时间(纳秒)
        long startTime=System.nanoTime();
        //输入k,n的值调用computSum进行计算k方幂的和序列的第N项的值
        sum = computerSum(k,n);
        //获取结束时间(纳秒)
        long endTime = System.nanoTime();
        System.out.println("程序运行时间为："+(endTime-startTime)+" ns(纳秒)");
        System.out.println(k+"的方幂及所有有限个互不相等的"+k+"的方幂之和构成一个递增的序列，序列第"+number+"项的值为：");
        System.out.println(sum);
    }

    /**
     * 项数	    1   2	   3	    4	  5	        6
     * 2进制数	1	10	   11	    100	  101	    110
     * 构造数	2^0	2^1	   2^1+2^0	2^2	  2^2+2^0   2^2+2^1
     * 实际数	1	3	   4	    9	  10	    12
     * 构造数	3^0	3^1	   3^1+3^0	3^2	  3^2+3^0	3^2+3^1
     * 算法思想分析：通过规律发现项数n的二进制数对应的构造数对应实际k对应的构造数
     * 所以只要求出项数（n）的2进制数，由此就能得到2进制数的构造数中每个数所所对应的幂次数，
     * 就能求出这个k方幂的和序列的第N项的值。
     * 该算法的时间复杂度为循环计算二进制数组中的10进制值的次数为O(array.lenght)
     * 也就是说该算法的时间复杂度为O(n)
     * 该算法的空间复杂度为创建数组array的元素个数O(array.lenght)
     * 也就是说该算法的空间复杂度为O(n)
     * @param k
     * @param n
     * @return
     */
    public static long computerSum(int k,int n){


        //定义一个数组用来存放二进制数
        int[] array = new int[1000];
        //定义sum存储最终值，定义flag存储数组下标
        long sum = 0;
        int flag = 0;
        //求出对应的二进制数并按照数组序号存入数组中。
        while (n>0)
        {
            array[flag] = n%2;
            n = n/2;
            //数组下标递增
            flag++;
        }
        //如果二进制数为1就要计算出对应构造数的幂次方的值，并且把他们相加，循环结束之后输出的结果就是我们所求的实际数。
        for (int i = 0; i < flag; i++)
        {
            if (array[i] == 1)
            {
//                sum += add(i,k);
                //Math.pow(k,i)计算k的i次方的值
                sum += (Math.pow(k,i));
            }
        }
        return sum;
    }

    /**
     *计算出具体二进制数为1项时的构造幂次方的值，实际原理为：
     * 以数组序号flag为基准，第array(flag)项为1的话，就要把该k乘以flag(数组下标)次方，
     * 所得就为构造数对应2进制数为1项的值。
     * @param n
     * @param k
     * @return 二进制数为1就要计算出对应构造数的幂次方的值
     */
    public static long add(int n,int k)
    {
        long s = 1;
        for (int i = 0; i < n; i++) {
            s *= k;
        }
        return s;
    }

    /**
     * 判断一个数是否为正整数
     * @param num
     * @return 返回true代表为正整数否则反之
     */
    public static boolean isNumeric(int num) {
        String str;
        str = String.valueOf(num);
        for (int i = str.length(); --i >= 0; ) {
            if (!Character.isDigit(str.charAt(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 校正输入参数k是否符合要求：正整数 k(3<=k<=15)
     * @param k
     * @return
     */
    public static boolean isInputK(int k) {
        if(!isNumeric(k))
        {
            System.out.println("请输入正整数！");
            return false;
        } else if(k < 3 || k > 15)
        {
            System.out.println("请输入大与3并且小与15的正整数！");
            return false;
        }
        return true;
    }
}
